// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"fmt"
	"math"
	"math/rand"
)

// Point 结构体
type Point struct {
	X, Y float64
}

// 表示一组点的 Cluster 结构体
type Cluster struct {
	Center Point
	Points []Point
}

// 执行 KMeans 集群算法，将点分组到指定数量的集群中
func KMeans(points []Point, k int) []Cluster {
	// 创建一个包含 k 个空集群的切片
	clusters := make([]Cluster, k)

	// 使用随机中心初始化集群
	for i := range clusters {
		clusters[i].Center = Point{X: rand.Float64(), Y: rand.Float64()}
	}

	// 直到所有集群的中心收敛到一个稳定的位置
	for {
		// 将每个点分配给最近的集群
		for i := range points {
			nearest := 0
			nearestDist := math.Inf(1)
			// 为当前点找到最近的集群中心
			for j := range clusters {
				dist := distance(points[i], clusters[j].Center)
				if dist < nearestDist {
					nearest = j
					nearestDist = dist
				}
			}
			// 将当前点添加到最近的集群中
			clusters[nearest].Points = append(clusters[nearest].Points, points[i])
		}

		// 重新计算所有集群的中心。如果任何集群的中心发生变化，则继续聚类
		changed := false
		for i := range clusters {
			if len(clusters[i].Points) > 0 {
				// 计算当前集群中所有点的均值作为新的中心
				mean := Point{X: 0, Y: 0}
				for _, p := range clusters[i].Points {
					mean.X += p.X
					mean.Y += p.Y
				}
				mean.X /= float64(len(clusters[i].Points))
				mean.Y /= float64(len(clusters[i].Points))
				// 如果新中心与当前中心不同，则更新中心并继续聚类
				if distance(mean, clusters[i].Center) > 1e-6 {
					changed = true
					clusters[i].Center = mean
				}
				// 重置当前集群中的点
				clusters[i].Points = nil
			}
		}

		// 如果所有集群的中心都没有改变，则停止聚类并返回簇集群
		if !changed {
			break
		}
	}

	return clusters
}

// 距离函数计算两点之间的欧氏距离
func distance(a, b Point) float64 {
	return math.Sqrt((a.X-b.X)*(a.X-b.X) + (a.Y-b.Y)*(a.Y-b.Y))
}

func main() {
	// 创建一个包含 10 个点的切片
	points := []Point{
		{X: 0, Y: 0},
		{X: 1, Y: 0},
		{X: 0, Y: 1},
		{X: 1, Y: 1},
		{X: 2, Y: 2},
		{X: 3, Y: 3},
		{X: 4, Y: 4},
		{X: 5, Y: 5},
		{X: 6, Y: 6},
		{X: 7, Y: 7}}
	clusters := KMeans(points, 2)
	for i, c := range clusters {
		fmt.Printf("群集 %d：中心=%v，点=%v\n", i, c.Center, c.Points)
	}
}

//$ go run kMeans.go
//群集 0：中心={5 5}，点=[]
//群集 1：中心={0.8 0.8}，点=[]
